package leetcode.year2021.month11;

// 221. 最大正方形
public class _04_1MaximalSquare221 {
  public int maximalSquare(char[][] matrix) {
    // 动态规划： 以dp[i][j]表示自己右下结尾的最大的边长是多少
    // 可以得出动态转移方程 如果matrix[i][j] == 0 说明 dp[i][j] == 0;
    // 否则 dp[i][j] = Math.min(dp[i-1][j-1] dp[i][j-1] dp[i-1][j]) + 1
    int maxBoard = 0;
    int[][] dp = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
      if (matrix[i][0] == '1'){
        dp[i][0] = 1;
        maxBoard = 1;
      }
    }
    for (int j = 0; j < matrix[0].length; j++) {
      if (matrix[0][j] == '1'){
        dp[0][j] = 1;
        maxBoard = 1;
      }
    }
    for (int i = 1; i < matrix.length; i++) {
      for (int j = 1; j < matrix[0].length; j++) {
        if (matrix[i][j] == '0'){
          dp[i][j] = 0;
        } else {
          dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1]) + 1;
          maxBoard = Math.max(maxBoard,dp[i][j]);
        }
      }
    }
    return maxBoard * maxBoard;
  }

  /**
   * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
   *
   *
   *
   * 示例 1：
   * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
   * 输出：4
   *
   * 输入：matrix = [["0","1"],["1","0"]]
   * 输出：1
   * 示例 3：
   *
   * 输入：matrix = [["0"]]
   * 输出：0
   *  
   *
   * 提示：
   *
   * m == matrix.length
   * n == matrix[i].length
   * 1 <= m, n <= 300
   * matrix[i][j] 为 '0' 或 '1'
   */
}
